package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

import java.util.*;

/**
 * 257.二叉树的所有路径（回溯）
 */
public class BiTree12_BinaryTreePaths2 {
    public static void main(String[] args) {
        // 创建一棵二叉树
        List<Integer> nodeList = Arrays.asList(1, 2, 3, null, 5);
        TreeNode root = BiTreeUtil.createBiTreeByRecursion(nodeList);
        System.out.println("先序遍历：" + BiTreeUtil.preorderTraversal(root));
        // 二叉树的所有路径
        System.out.println(binaryTreePaths(root));
    }

    /**
     * 回溯
     */
    private static List<String> binaryTreePaths(TreeNode root) {
        List<String> pathList = new ArrayList<>();
        traversal(root, new StringBuilder(), pathList);
        // traversal2(root, new ArrayList<>(), pathList);
        return pathList;
    }

    /**
     * 回溯1：重置递归每一层 StringBuilder 的状态
     */
    private static void traversal(TreeNode root, StringBuilder pathString, List<String> pathList) {
        if (root == null) {
            return;
        }
        // 记录进入这一层递归时的路径长度
        int len = pathString.length();
        pathString.append(root.val);
        // 叶子节点添加到路径列表中
        if (root.left == null && root.right == null) {
            pathList.add(pathString.toString());
        } else {
            // 根节点不会添加->
            pathString.append("->");
            // 递归遍历左右子树
            traversal(root.left, pathString, pathList);
            traversal(root.right, pathString, pathList);
        }
        // 回溯到这一层递归开始时的状态
        pathString.setLength(len);
    }

    /**
     * 回溯2：退回上一层前去除当前层添加的节点
     */
    private static void traversal2(TreeNode root, List<Integer> pathNodeList, List<String> pathList) {
        if (root == null) {
            return;
        }
        // 添加路径节点
        pathNodeList.add(root.val);
        // 叶子结点，则拼接路径放入结果列表中
        if (root.left == null && root.right == null) {
            pathList.add(buildPath(pathNodeList));
        } else {
            traversal2(root.left, pathNodeList, pathList);
            traversal2(root.right, pathNodeList, pathList);
        }
        // 回溯：去除最后一个节点
        pathNodeList.remove(pathNodeList.size() - 1);
    }

    // 根据节点列表拼接叶子节点路径
    private static String buildPath(List<Integer> nodes) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < nodes.size(); i++) {
            sb.append(nodes.get(i));
            if (i != nodes.size() - 1) {
                sb.append("->");
            }
        }
        return sb.toString();
    }

}
